//===--- ConstraintGraph.h - Constraint Graph -------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file defines the \c ConstraintGraph class, which describes the
// relationships among the type variables within a constraint system.
//
//===----------------------------------------------------------------------===//
#ifndef POLARPHP_SEMA_INTERNAL_CONSTRAINT_GRAPH_H
#define POLARPHP_SEMA_INTERNAL_CONSTRAINT_GRAPH_H

#include "polarphp/basic/Debug.h"
#include "polarphp/basic/LLVM.h"
#include "polarphp/ast/Identifier.h"
#include "polarphp/ast/Type.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Support/Compiler.h"
#include <functional>
#include <utility>

namespace polar {

class Type;
class TypeBase;
class TypeVariableType;

namespace constraints {

class Constraint;
class ConstraintGraph;
class ConstraintGraphScope;
class ConstraintSystem;

/// A single node in the constraint graph, which represents a type variable.
class ConstraintGraphNode {
   /// Describes information about an adjacency between two type variables.
   struct Adjacency {
      /// Index into the vector of adjacent type variables, \c Adjacencies.
      unsigned Index;

      /// The number of constraints that link this type variable to the
      /// enclosing node.
      unsigned NumConstraints;

      bool empty() const {
         return NumConstraints == 0;
      }
   };

public:
   explicit ConstraintGraphNode(TypeVariableType *typeVar) : TypeVar(typeVar) { }

   ConstraintGraphNode(const ConstraintGraphNode&) = delete;
   ConstraintGraphNode &operator=(const ConstraintGraphNode&) = delete;

   /// Retrieve the type variable this node represents.
   TypeVariableType *getTypeVariable() const { return TypeVar; }

   /// Retrieve the set of constraints that mention this type variable.
   ///
   /// These are the hyperedges of the graph, connecting this node to
   /// various other nodes.
   ArrayRef<Constraint *> getConstraints() const { return Constraints; }

   /// Retrieve the set of type variables to which this node is adjacent.
   ArrayRef<TypeVariableType *> getAdjacencies() const {
      return Adjacencies;
   }

   /// Retrieve the set of type variables that are adjacent due to fixed
   /// bindings.
   ArrayRef<TypeVariableType *> getFixedBindings() const {
      return FixedBindings;
   }

   /// Retrieve all of the type variables in the same equivalence class
   /// as this type variable.
   ArrayRef<TypeVariableType *> getEquivalenceClass() const;

private:
   /// Retrieve all of the type variables in the same equivalence class
   /// as this type variable.
   ArrayRef<TypeVariableType *> getEquivalenceClassUnsafe() const;

   /// Add a constraint to the list of constraints.
   void addConstraint(Constraint *constraint);

   /// Remove a constraint from the list of constraints.
   ///
   /// Note that this only removes the constraint itself; it does not
   /// remove the corresponding adjacencies.
   void removeConstraint(Constraint *constraint);

   /// Retrieve adjacency information for the given type variable.
   Adjacency &getAdjacency(TypeVariableType *typeVar);

   /// Modify the adjacency information for the given type variable
   /// directly. If the adjacency becomes empty afterward, it will be
   /// removed.
   void modifyAdjacency(TypeVariableType *typeVar,
                        llvm::function_ref<void(Adjacency &adj)> modify);

   /// Add an adjacency to the list of adjacencies.
   void addAdjacency(TypeVariableType *typeVar);

   /// Remove an adjacency from the list of adjacencies.
   void removeAdjacency(TypeVariableType *typeVar);

   /// Add the given type variables to this node's equivalence class.
   void addToEquivalenceClass(ArrayRef<TypeVariableType *> typeVars);

   /// Add a type variable related to this type variable through fixed
   /// bindings.
   void addFixedBinding(TypeVariableType *typeVar);

   /// Remove a type variable from the fixed-binding relationship.
   void removeFixedBinding(TypeVariableType *typeVar);

   /// The type variable this node represents.
   TypeVariableType *TypeVar;

   /// The vector of constraints that mention this type variable, in a stable
   /// order for iteration.
   SmallVector<Constraint *, 2> Constraints;

   /// A mapping from the set of constraints that mention this type variable
   /// to the index within the vector of constraints.
   llvm::SmallDenseMap<Constraint *, unsigned, 2> ConstraintIndex;

   /// The set of adjacent type variables, in a stable order.
   SmallVector<TypeVariableType *, 2> Adjacencies;

   /// A mapping from each of the type variables adjacent to this
   /// type variable to the index of the adjacency information in
   /// \c Adjacencies.
   llvm::SmallDenseMap<TypeVariableType *, Adjacency, 2> AdjacencyInfo;

   /// The set of type variables that occur within the fixed binding of
   /// this type variable.
   SmallVector<TypeVariableType *, 2> FixedBindings;

   /// All of the type variables in the same equivalence class as this
   /// representative type variable.
   ///
   /// Note that this field is only valid for type variables that
   /// are representatives of their equivalence classes.
   mutable SmallVector<TypeVariableType *, 2> EquivalenceClass;

   /// Print this graph node.
   void print(llvm::raw_ostream &out, unsigned indent,
              PrintOptions PO = PrintOptions()) const;

   POLAR_DEBUG_DUMP;

   /// Verify the invariants of this node within the given constraint graph.
   void verify(ConstraintGraph &cg);

   friend class ConstraintGraph;
};

/// A graph that describes the relationships among the various type variables
/// and constraints within a constraint system.
///
/// The constraint graph is a hypergraph where the nodes are type variables and
/// the edges are constraints. Any given constraint connects a type variable to
/// zero or more other type variables. Because these adjacencies are as
/// important as the edges themselves and are expensive to calculate from the
/// constraints, each node in the graph tracks both its edges (constraints) and
/// its adjacencies (the type variables) separately.
class ConstraintGraph {
public:
   /// Constraint a constraint graph for the given constraint system.
   ConstraintGraph(ConstraintSystem &cs);

   /// Destroy the given constraint graph.
   ~ConstraintGraph();

   ConstraintGraph(const ConstraintGraph &) = delete;
   ConstraintGraph &operator=(const ConstraintGraph &) = delete;


   /// Retrieve the constraint system this graph describes.
   ConstraintSystem &getConstraintSystem() const { return CS; }

   /// Access the node corresponding to the given type variable.
   ConstraintGraphNode &operator[](TypeVariableType *typeVar) {
      return lookupNode(typeVar).first;
   }

   /// Retrieve the node and index corresponding to the given type variable.
   std::pair<ConstraintGraphNode &, unsigned>
   lookupNode(TypeVariableType *typeVar);

   /// Add a new constraint to the graph.
   void addConstraint(Constraint *constraint);

   /// Remove a constraint from the graph.
   void removeConstraint(Constraint *constraint);

   /// Merge the two nodes for the two given type variables.
   ///
   /// The type variables must actually have been merged already; this
   /// operation merges the two nodes.
   void mergeNodes(TypeVariableType *typeVar1, TypeVariableType *typeVar2);

   /// Bind the given type variable to the given fixed type.
   void bindTypeVariable(TypeVariableType *typeVar, Type fixedType);

   /// Describes which constraints \c gatherConstraints should gather.
   enum class GatheringKind {
      /// Gather constraints associated with all of the variables within the
      /// same equivalence class as the given type variable.
         EquivalenceClass,
      /// Gather all constraints that mention this type variable or type variables
      /// that it is equivalent to.
         AllMentions,
   };

   /// Gather the set of constraints that involve the given type variable,
   /// i.e., those constraints that will be affected when the type variable
   /// gets merged or bound to a fixed type.
   llvm::TinyPtrVector<Constraint *>
   gatherConstraints(TypeVariableType *typeVar,
                     GatheringKind kind,
                     llvm::function_ref<bool(Constraint *)> acceptConstraint =
                     [](Constraint *constraint) { return true; });

   /// Retrieve the type variables that correspond to nodes in the graph.
   ///
   /// The subscript operator can be used to retrieve the nodes that
   /// correspond to these type variables.
   ArrayRef<TypeVariableType *> getTypeVariables() const {
      return TypeVariables;
   }

   /// Describes a single component, as produced by the connected components
   /// algorithm.
   struct Component {
      /// The type variables in this component.
      TinyPtrVector<TypeVariableType *> typeVars;

      /// The original index of this component in the list of components,
      /// used to provide the index of where the partial solutions will occur.
      /// FIXME: This is needed due to some ordering dependencies in the
      /// merging of partial solutions, which appears to also be related
      /// DisjunctionStep::pruneOverloads() short-circuiting. It should be
      /// removed.
      unsigned solutionIndex;

   private:
      /// The number of disjunctions in this component.
      unsigned numDisjunctions = 0;

      /// The constraints in this component.
      TinyPtrVector<Constraint *> constraints;

   public:
      /// The set of components that this component depends on, such that
      /// the partial solutions of the those components need to be available
      /// before this component can be solved.
      ///
      /// FIXME: Use a TinyPtrVector here.
      std::vector<unsigned> dependsOn;

      Component(unsigned solutionIndex) : solutionIndex(solutionIndex) { }

      /// Whether this component represents an orphaned constraint.
      bool isOrphaned() const {
         return typeVars.empty();
      }

      /// Add a constraint.
      void addConstraint(Constraint *constraint);

      const TinyPtrVector<Constraint *> &getConstraints() const {
         return constraints;
      }

      unsigned getNumDisjunctions() const { return numDisjunctions; }
   };

   /// Compute the connected components of the graph.
   ///
   /// \param typeVars The type variables that should be included in the
   /// set of connected components that are returned.
   ///
   /// \returns the connected components of the graph, where each component
   /// contains the type variables and constraints specific to that component.
   SmallVector<Component, 1> computeConnectedComponents(
      ArrayRef<TypeVariableType *> typeVars);

   /// Retrieve the set of "orphaned" constraints, which are known to the
   /// constraint graph but have no type variables to anchor them.
   ArrayRef<Constraint *> getOrphanedConstraints() const {
      return OrphanedConstraints;
   }

   /// Replace the orphaned constraints with the constraints in the given list,
   /// returning the old set of orphaned constraints.
   SmallVector<Constraint *, 4> takeOrphanedConstraints() {
      auto result = std::move(OrphanedConstraints);
      OrphanedConstraints.clear();
      return result;
   }

   /// Set the orphaned constraints.
   void setOrphanedConstraints(SmallVector<Constraint *, 4> &&newConstraints) {
      OrphanedConstraints = std::move(newConstraints);
   }

   /// Set the list of orphaned constraints to a single constraint.
   ///
   /// If \c orphaned is null, just clear out the list.
   void setOrphanedConstraint(Constraint *orphaned) {
      OrphanedConstraints.clear();
      if (orphaned)
         OrphanedConstraints.push_back(orphaned);
   }

   /// Print the graph.
   void print(ArrayRef<TypeVariableType *> typeVars, llvm::raw_ostream &out);
   void dump(llvm::raw_ostream &out);

   // FIXME: Potentially side-effectful.
   POLAR_DEBUG_HELPER(void dump());

   /// Print the connected components of the graph.
   void printConnectedComponents(ArrayRef<TypeVariableType *> typeVars,
                                 llvm::raw_ostream &out);

   // FIXME: Potentially side-effectful.
   POLAR_DEBUG_HELPER(void dumpConnectedComponents());

   /// Verify the invariants of the graph.
   void verify();

   /// Optimize the constraint graph by eliminating simple transitive
   /// connections between nodes.
   void optimize();

private:
   /// Remove the node corresponding to the given type variable.
   ///
   /// This operation assumes that the any constraints that refer to
   /// this type variable have been or will be removed before other
   /// graph queries are performed.
   ///
   /// Note that this change is not recorded and cannot be undone. Use with
   /// caution.
   void removeNode(TypeVariableType *typeVar);

   /// Unbind the given type variable from the given fixed type.
   ///
   /// Note that this change is not recorded and cannot be undone. Use with
   /// caution.
   void unbindTypeVariable(TypeVariableType *typeVar, Type fixedType);

   /// Perform edge contraction on the constraint graph, merging equivalence
   /// classes until a fixed point is reached.
   bool contractEdges();

   /// To support edge contraction, remove a constraint from both the constraint
   /// graph and its enclosing constraint system.
   void removeEdge(Constraint *constraint);

   /// The constraint system.
   ConstraintSystem &CS;

   /// The type variables in this graph, in stable order.
   std::vector<TypeVariableType *> TypeVariables;

   /// Constraints that are "orphaned" because they contain no type variables.
   SmallVector<Constraint *, 4> OrphanedConstraints;

   /// Increment the number of constraints considered per attempt
   /// to contract constrant graph edges.
   void incrementConstraintsPerContractionCounter();

   /// The kind of change made to the graph.
   enum class ChangeKind {
      /// Added a type variable.
         AddedTypeVariable,
      /// Added a new constraint.
         AddedConstraint,
      /// Removed an existing constraint
         RemovedConstraint,
      /// Extended the equivalence class of a type variable.
         ExtendedEquivalenceClass,
      /// Added a fixed binding for a type variable.
         BoundTypeVariable,
   };

   /// A change made to the constraint graph.
   ///
   /// Each change can be undone (once, and in reverse order) by calling the
   /// undo() method.
   class Change {
      /// The kind of change.
      ChangeKind Kind;

      union {
         TypeVariableType *TypeVar;
         Constraint *TheConstraint;

         struct {
            /// The type variable whose equivalence class was extended.
            TypeVariableType *TypeVar;

            /// The previous size of the equivalence class.
            unsigned PrevSize;
         } EquivClass;

         struct {
            /// The type variable being bound to a fixed type.
            TypeVariableType *TypeVar;

            /// The fixed type to which the type variable was bound.
            TypeBase *FixedType;
         } Binding;
      };

   public:
      Change() : Kind(ChangeKind::AddedTypeVariable), TypeVar(nullptr) { }

      /// Create a change that added a type variable.
      static Change addedTypeVariable(TypeVariableType *typeVar);

      /// Create a change that added a constraint.
      static Change addedConstraint(Constraint *constraint);

      /// Create a change that removed a constraint.
      static Change removedConstraint(Constraint *constraint);

      /// Create a change that extended an equivalence class.
      static Change extendedEquivalenceClass(TypeVariableType *typeVar,
                                             unsigned prevSize);

      /// Create a change that bound a type variable to a fixed type.
      static Change boundTypeVariable(TypeVariableType *typeVar, Type fixed);

      /// Undo this change, reverting the constraint graph to the state it
      /// had prior to this change.
      ///
      /// Changes must be undone in stack order.
      void undo(ConstraintGraph &cg);
   };

   /// The currently active scope, or null if we aren't tracking changes made
   /// to the constraint graph.
   ConstraintGraphScope *ActiveScope = nullptr;

   /// The set of changes made to this constraint graph.
   ///
   /// As the constraint graph is extended and mutated, additional changes are
   /// introduced into this vector. Each scope
   llvm::SmallVector<Change, 4> Changes;

   friend class ConstraintGraphScope;
};

} // end namespace constraints
} // end namespace polar

#endif // LLVM_POLARPHP_SEMA_INTERNAL_CONSTRAINT_GRAPH_H
